package ustc.xiaoyang.karl.slidingwindows;

/**
 * 76.最小覆盖子串 hard
 */
public class MinimumCoveringSubstring76 {
    public static void main(String[] args) {

        System.out.println(new MinimumCoveringSubstring76().minWindow("ADOBECODEBANC","ABC"));
    }
    public String minWindow(String s,String t)
    {
        int[] cnt_s = new int[128];
        int[] cnt_t = new int[128];
        for(char c : t.toCharArray()){
            cnt_t[c]++;
        }
        int ans_l = -1;
        int ans_r = s.length();
        int left = 0;
        for (int right = 0; right < s.length() ; right++) {
            cnt_s[s.charAt(right)]++;
            while(check(cnt_s,cnt_t)){
                if(right - left < ans_r - ans_l){
                    ans_l = left;
                    ans_r = right;
                }
                cnt_s[s.charAt((left))]--;
                left++;
            }
        }
        return ans_l == -1 ? "" : s.substring(ans_l,ans_r + 1);
    }
    public boolean check(int[] cnt_s,int [] cnt_t){
        for (int i = 'A'; i <= 'Z'; i++) {
            if(cnt_s[i] < cnt_t[i])
                return false;
        }
        for (int i = 'a'; i <= 'z'; i++){
            if(cnt_s[i] < cnt_t[i])
                return false;
        }
        return true;
    }

}
